Title

Similar Question

Solution Tips

方案一: 01 背包

var findMaxForm = function(strs, m, n) {
    // 感觉总算是遇到一道标准一点的背包问题了
    // 相当于是有两个重量维度, 一个是 m, 一个是 n
    // 能装最多的元素的个数是多少
    const len = strs.length;
    // 处理出 weightM 和 weightN
    const weightM = Array.from({ length: len });
    const weightN = Array.from({ length: len });
    for (let i = 0; i < len; i++) {
        const str = strs[i];
        let m = 0;
        let n = 0;
        for (let j = 0; j < str.length; j++) {
            str[j] === '0' ? m++ : n++
        }
        weightM[i] = m;
        weightN[i] = n;
    }

    // 套用背包模板
    // dp[j][k] 表示 0 的个数为 j 个, 1 的个数为 k 个数, 能放入的长度
    // m 和 n 都 + 1 是为了表明最大重量可以刚好是 m 和 n
    const dp = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => 0));
    for (let i = 0; i < len; i++) {
        for (let j = m; j >= weightM[i]; j--) {
            for (let k = n; k >= weightN[i]; k--) {
                dp[j][k] = Math.max(dp[j][k], dp[j - weightM[i]][k - weightN[i]] + 1);
            }
        }
        // console.log(dp.concat()) //调试
    }

    return dp[m][n];
};

let strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
console.log(findMaxForm(strs, m, n));